package com.julius.design.suanfa.linked;


import java.util.HashMap;
import java.util.Map;

/**
 * @author julius
 * @date 2021-10-20 上午 10:21
 * <p>
 *     翻转链表
 * </p>
 */
public class ReverseLinked {

    /**
     * 翻转链表
     * @param head 头节点
     * @return 翻转后的头结点
     */
    public static ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        /*
                思路一：
                    使用栈的先进后出特性翻转  但是利用了额外的栈空间
                思路二：
                    原地翻转
         */
        ListNode pre = head;
        ListNode cur = pre.next;
        while(cur != null){
            if(pre == head){
                pre.next = null;
            }
            ListNode next = cur.next;
            if(next == null){
                cur.next = pre;
                break;
            }
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return cur;
    }












    public static class ListNode{

        int val;

        ListNode next;

        ListNode(int val){
            this.val = val;
        }
    }
}
